

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">

<html>


<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">

<base target="_top">
<style type="text/css">
  

/* default css */

table {
  font-size: 1em;
  line-height: inherit;
  border-collapse: collapse;
}


tr {
  
  text-align: left;
  
}


div, address, ol, ul, li, option, select {
  margin-top: 0px;
  margin-bottom: 0px;
}

p {
  margin: 0px;
}


pre {
  font-family: Courier New;
  white-space: pre-wrap;
  margin:0;
}

body {
  margin: 6px;
  padding: 0px;
  font-family: Verdana, sans-serif;
  font-size: 10pt;
  background-color: #ffffff;
}


img {
  -moz-force-broken-image-icon: 1;
}

@media screen {
  html.pageview {
    background-color: #f3f3f3 !important;
  }

  

  body {
    min-height: 1100px;
    
    counter-reset: __goog_page__;
  }
  * html body {
    height: 1100px;
  }
  .pageview body {
    border-top: 1px solid #ccc;
    border-left: 1px solid #ccc;
    border-right: 2px solid #bbb;
    border-bottom: 2px solid #bbb;
    width: 648px !important;
    margin: 15px auto 25px;
    padding: 40px 50px;
  }
  /* IE6 */
  * html {
    overflow-y: scroll;
  }
  * html.pageview body {
    overflow-x: auto;
  }
  /* Prevent repaint errors when scrolling in Safari. This "Star-7" css hack
     targets Safari 3.1, but not WebKit nightlies and presumably Safari 4.
     That's OK because this bug is fixed in WebKit nightlies/Safari 4 :-). */
  html*#wys_frame::before {
    content: '\A0';
    position: fixed;
    overflow: hidden;
    width: 0;
    height: 0;
    top: 0;
    left: 0;
  }
  
  

  
    .writely-callout-data {
      display: none;
      *display: inline-block;
      *width: 0;
      *height: 0;
      *overflow: hidden;
    }
    .writely-footnote-marker {
      background-image: url('MISSING');
      background-color: transparent;
      background-repeat: no-repeat;
      width: 7px;
      overflow: hidden;
      height: 16px;
      vertical-align: top;

      
      -moz-user-select: none;
    }
    .editor .writely-footnote-marker {
      cursor: move;
    }
    .writely-footnote-marker-highlight {
      background-position: -15px 0;
      -moz-user-select: text;
    }
    .writely-footnote-hide-selection ::-moz-selection, .writely-footnote-hide-selection::-moz-selection {
      background: transparent;
    }
    .writely-footnote-hide-selection ::selection, .writely-footnote-hide-selection::selection {
      background: transparent;
    }
    .writely-footnote-hide-selection {
      cursor: move;
    }

    
    .editor .writely-comment-yellow {
      background-color: #FF9;
      background-position: -240px 0;
    }
    .editor .writely-comment-yellow-hover {
      background-color: #FF0;
      background-position: -224px 0;
    }
    .editor .writely-comment-blue {
      background-color: #C0D3FF;
      background-position: -16px 0;
    }
    .editor .writely-comment-blue-hover {
      background-color: #6292FE;
      background-position: 0 0;
    }
    .editor .writely-comment-orange {
      background-color: #FFDEAD;
      background-position: -80px 0;
    }
    .editor .writely-comment-orange-hover {
      background-color: #F90;
      background-position: -64px 0;
    }
    .editor .writely-comment-green {
      background-color: #99FBB3;
      background-position: -48px 0;
    }
    .editor .writely-comment-green-hover {
      background-color: #00F442;
      background-position: -32px 0;
    }
    .editor .writely-comment-cyan {
      background-color: #CFF;
      background-position: -208px 0;
    }
    .editor .writely-comment-cyan-hover {
      background-color: #0FF;
      background-position: -192px 0;
    }
    .editor .writely-comment-purple {
      background-color: #EBCCFF;
      background-position: -144px 0;
    }
    .editor .writely-comment-purple-hover {
      background-color: #90F;
      background-position: -128px 0;
    }
    .editor .writely-comment-magenta {
      background-color: #FCF;
      background-position: -112px 0;
    }
    .editor .writely-comment-magenta-hover {
      background-color: #F0F;
      background-position: -96px 0;
    }
    .editor .writely-comment-red {
      background-color: #FFCACA;
      background-position: -176px 0;
    }
    .editor .writely-comment-red-hover {
      background-color: #FF7A7A;
      background-position: -160px 0;
    }

    .editor .writely-comment-marker {
      background-image: url('MISSING');
      background-color: transparent;
      padding-right: 11px;
      background-repeat: no-repeat;
      width: 16px;
      height: 16px;
      -moz-user-select: none;
    }

    .editor .writely-comment-hidden {
      padding: 0;
      background: none;
    }
    .editor .writely-comment-marker-hidden {
      background: none;
      padding: 0;
      width: 0;
    }
    .editor .writely-comment-none {
      opacity: .2;
      filter:progid:DXImageTransform.Microsoft.Alpha(opacity=20);
      -moz-opacity: .2;
    }
    .editor .writely-comment-none-hover {
      opacity: .2;
      filter:progid:DXImageTransform.Microsoft.Alpha(opacity=20);
      -moz-opacity: .2;
    }
  


  
  .br_fix br:not(:-moz-last-node):not(:-moz-first-node) {
    
    position:relative;
    
    left: -1ex
    
  }
  
  .br_fix br+br {
    position: static !important
  }
}

h6 { font-size: 8pt }
h5 { font-size: 8pt }
h4 { font-size: 10pt }
h3 { font-size: 12pt }
h2 { font-size: 14pt }
h1 { font-size: 18pt }

blockquote {padding: 10px; border: 1px #DDD dashed }

a img {border: 0}

.pb {
  border-width: 0;
  page-break-after: always;
  /* We don't want this to be resizeable, so enforce a width and height
     using !important */
  height: 1px !important;
  width: 100% !important;
}

.editor .pb {
  border-top: 1px dashed #C0C0C0;
  border-bottom: 1px dashed #C0C0C0;
}

div.google_header, div.google_footer {
  position: relative;
  margin-top: 1em;
  margin-bottom: 1em;
}


/* Table of contents */
.editor div.writely-toc {
  background-color: #f3f3f3;
  border: 1px solid #ccc;
}
.writely-toc > ol {
  padding-left: 3em;
  font-weight: bold;
}
ol.writely-toc-subheading {
  padding-left: 1em;
  font-weight: normal;
}
/* IE6 only */
* html writely-toc ol {
  list-style-position: inside;
}
.writely-toc-none {
  list-style-type: none;
}
.writely-toc-decimal {
  list-style-type: decimal;
}
.writely-toc-upper-alpha {
  list-style-type: upper-alpha;
}
.writely-toc-lower-alpha {
  list-style-type: lower-alpha;
}
.writely-toc-upper-roman {
  list-style-type: upper-roman;
}
.writely-toc-lower-roman {
  list-style-type: lower-roman;
}
.writely-toc-disc {
  list-style-type: disc;
}

/* Ordered lists converted to numbered lists can preserve ordered types, and
   vice versa. This is confusing, so disallow it */
ul[type="i"], ul[type="I"], ul[type="1"], ul[type="a"], ul[type="A"] {
  list-style-type: disc;
}

ol[type="disc"], ol[type="circle"], ol[type="square"] {
  list-style-type: decimal;
}

/* end default css */


  /* default print css */
  
  @media print {
    body {
      padding: 0;
      margin: 0;
    }

    div.google_header, div.google_footer {
      display: block;
      min-height: 0;
      border: none;
    }

    div.google_header {
      flow: static(header);
    }

    /* used to insert page numbers */
    div.google_header::before, div.google_footer::before {
      position: absolute;
      top: 0;
    }

    div.google_footer {
      flow: static(footer);
    }

    /* always consider this element at the start of the doc */
    div#google_footer {
      flow: static(footer, start);
    }

    span.google_pagenumber {
      content: counter(page);
    }

    span.google_pagecount {
      content: counter(pages);
    }


    callout.google_footnote {
      
      display: prince-footnote;
      footnote-style-position: inside;
      /* These styles keep the footnote from taking on the style of the text
         surrounding the footnote marker. They can be overridden in the
         document CSS. */
      color: #000;
      font-family: Times New Roman;
      font-size: 12.0pt;
      font-weight: normal;
    }

    /* Table of contents */
    #WritelyTableOfContents a::after {
      content: leader('.') target-counter(attr(href), page);
    }

    #WritelyTableOfContents a {
      text-decoration: none;
      color: black;
    }
  }

  @page {
    @top {
      content: flow(header);
    }
    @bottom {
      content: flow(footer);
    }
    @footnotes {
      border-top: solid black thin;
      padding-top: 8pt;
    }
  }
  /* end default print css */


/* custom css */


/* end custom css */

/* ui edited css */

body {
  font-family: Times New Roman;
  
  font-size: 12.0pt;
  line-height: normal;
  background-color: #ffffff;
}
/* end ui edited css */


/* editor CSS */
.editor a:visited {color: #551A8B}
.editor table.zeroBorder {border: 1px dotted gray}
.editor table.zeroBorder td {border: 1px dotted gray}
.editor table.zeroBorder th {border: 1px dotted gray}


.editor div.google_header, .editor div.google_footer {
  border: 2px #DDDDDD dashed;
  position: static;
  width: 100%;
  min-height: 2em;
}

.editor .misspell {background-color: yellow}

.editor .writely-comment {
  font-size: 9pt;
  line-height: 1.4;
  padding: 1px;
  border: 1px dashed #C0C0C0
}


/* end editor CSS */

</style>

  
  <title>lab04_otchet</title>

</head>

<body 
    
    >
    
    
    
<p align=center>
  <font size=3>Московский государственный технический университет им. Н. Э. Баумана</font>
</p>
<p align=center class=western>
  <br>
</p>
<p align=center class=western>
  <br>
</p>
<p align=center class=western>
  <br>
</p>
<p align=center class=western>
  <br>
</p>
<p align=center class=western>
  <br>
</p>
<p align=center class=western>
  <br>
</p>
<p align=center class=western>
  <br>
</p>
<p align=center class=western>
  <br>
</p>
<p align=center class=western>
  <br>
</p>
<p align=center class=western>
  <br>
</p>
<p align=center class=western>
  <br>
</p>
<p align=center class=western>
  <br>
</p>
<p align=center class=western>
  <br>
</p>
<p align=center class=western>
  <br>
</p>
<p align=center class=western>
  <br>
</p>
<p align=center class=western>
  <br>
</p>
<h2 class=western style=TEXT-ALIGN:center>
  Отчет по лабораторной работе №4 по дисциплине
</h2>
<div>
</div>
<p class=western style=TEXT-ALIGN:center>
  <font size=3><b>Интеллектуальные Системы</b></font>
</p>
<div style=TEXT-ALIGN:center>
</div>
<p class=western style=TEXT-ALIGN:center>
  <font size=3><b>«Решение задач с помощью генетических алгоритмов»</b></font>
</p>
<p align=center class=western>
  <br>
</p>
<p align=center class=western>
  <br>
</p>
<p align=center class=western>
  <br>
</p>
<p align=center class=western>
  <br>
</p>
<p align=center class=western>
  <br>
</p>
<p align=center class=western>
  <br>
</p>
<p align=center class=western>
  <br>
</p>
<p align=center class=western>
  <br>
</p>
<p align=center class=western>
  <br>
</p>
<p align=center class=western>
  <br>
</p>
<p align=center class=western>
  <br>
</p>
<p align=center class=western>
  <br>
</p>
<p align=center class=western>
  <br>
</p>
<h3 class=western style=MARGIN-RIGHT:0.26in>
  Разработал: студент группы ИУ5-82
</h3>
<p align=right class=western style=MARGIN-RIGHT:0.26in>
  <font size=3>Пояганов О.А.</font>
</p>
<p align=right class=western>
  <br>
</p>
<p align=center class=western>
  <br>
</p>
<p align=center class=western>
  <br>
</p>
<p align=center class=western>
  <br>
</p>
<p align=center class=western>
  <br>
</p>
<p align=center class=western>
  <br>
</p>
<p align=center class=western>
  <br>
</p>
<p align=center class=western>
  <br>
</p>
<p align=center class=western>
  <br>
</p>
<p align=center class=western>
  <br>
</p>
<p align=center class=western>
  <br>
</p>
<p align=center class=western>
  <br>
</p>
<p align=center class=western>
  <br>
</p>
<p align=center class=western>
  <br>
</p>
<p align=center class=western>
  <br>
</p>
<p align=center class=western>
  <br>
</p>
<p align=center class=western>
  <br>
</p>
<p align=center class=western>
  <br>
</p>
<p align=center class=western>
  <br>
</p>
<p align=center class=western>
  <font size=3>Москва 2009 г.</font>
</p>
<p align=justify class=western>
  <br>
</p>
<div dir=ltr id="Table of Contents1">
  <p class=western>
    <br>
    <br>
  </p>
</div>
<p align=justify class=western>
  <br>
</p>
<ol>
  <ol style=TEXT-ALIGN:left>
    <li>
      <h4 class=western style=TEXT-ALIGN:left>
        Цель работы.
      </h4>
    </li>
  </ol>
</ol>
<p class=western>
  <br>
</p>
<p align=justify>
  <font size=3>Ознакомиться с подходом к решению оптимизационных задач с помощью генетических алгоритмов (ГА).</font>
</p>
<p align=justify>
  <br>
</p>
<h4 class=western>
  1.2. Задания
</h4>
<p align=justify class=western>
  <br>
</p>
<p align=justify>
  <font size=3>В рамках лабораторной работы необходимо разработать компьютерную программу, которая осуществляет поиск кратчайшего пути для информационного пакета (сообщения) в компьютерной сети с помощью генетических алгоритмов. </font>
</p>
<p align=justify>
  <font size=3>Для проведения серии экспериментов программа должна позволять пользователю задавать топологию сети (пропускные способности каналов связи), содержащей не менее 10 компьютеров (серверов), а также указывать компьютер-отправитель и компьютер-получатель. На экране должны отображаться все представители (хромосомы) одного поколения. Переход к следующему поколению должен осуществляться в автоматическом режиме.</font>
</p>
<br>
<h4 class=western>
  2. Реализация задачи
</h4>
<p align=justify class=western>
  <br>
</p>
<h5 class=western>
  <font face="Times New Roman, serif">2.1. Описание предметной области и выбранной задачи.</font>
</h5>
<p align=justify class=western>
</p>
<p align=justify>
  <font face="Arial, sans-serif"><font size=3><font face="Times New Roman, serif">Программа осуществляет поиск кратчайшего пути для информационного пакета (сообщения) в компьютерной сети с помощью генетических алгоритмов. Пусть имеется сеть с заданной топологией, а также взвешенные дуги, отображающие связи между узлами сети (смысл значений весов дуг может выбираться для каждой конкретной задачи отдельно, но чаще всего это пропускная способность соответствующих каналов связи). Указаны отправитель и получатель пакета и задача состоит в том, чтобы найти кратчайший путь между ними, используя генетический алгоритм. </font></font></font>
</p>
<p align=justify class=western>
  <br>
</p>
<h5 class=western>
  <font face="Times New Roman, serif">2.2. Блок-схема с пояснениями выбранного ГА</font> <font face="Times New Roman, serif">и каждого оператора в отдельности</font>
</h5>
<p class=western>
  <br>
</p>
<p class=western>
  <font size=3>Были выбраны операторы скрещивания и мутации.</font>
</p>
<p>
  <font size=3>Оператор скрещивания работает следующим образом: для выбранной пары хромосом случайным образом генерируются начальный ген и количество обменов генов. После этого выбранные участки хромосом обмениваются.</font>
</p>
<p class=western>
  <font size=3>Оператор работает мутации следующим образом: в хромосоме в случайных позициях происходит замена узла на другой, номер которого генерируется случайным образом. Мутация происходит после скрещивания с вероятностью 40%</font>
</p>
<p align=justify class=western>
  <font size=3><font color=#000000>. Количество хромосом в популяции – задается в программе (по умолчанию 1000), длина хромосомы – задается в программе (по умолчанию 10 генов), для следующего поколения отбирается заданное число лучших хромосом.</font></font>
</p>
<p align=justify class=western>
  <img align=bottom height=649 name=Object1 src=lab04_otchet_images/dg9jvsbd_76f9kn4zgk_b.gif width=733>
</p>
<h5 class=western>
  <font face="Times New Roman, serif">2.3. Протоколы проведенных экспериментов</font>
</h5>
<p class=western>
  <br>
</p>
<p align=justify>
  <font face="Times New Roman, serif"><font size=3>Для проведения эксперимента использовались следующие исходные данные.</font></font>
</p>
<ul>
  <li>
    <p align=justify>
      <font face="Times New Roman, serif"><font size=3>Матрица путей графа сети (начальная вершина 0, конечная 9)</font></font>
    </p>
  </li>
</ul>
<p align=justify style=MARGIN-LEFT:0.64in>
  <img align=bottom border=0 height=577 name=graphics1 src=lab04_otchet_images/dg9jvsbd_77cz5b94hc_b.png width=533>
</p>
<p align=justify style=MARGIN-LEFT:0.64in>
  <img align=bottom border=0 height=459 name=graphics2 src=lab04_otchet_images/dg9jvsbd_78xkfn9cm_b.png width=618>
</p>
<p align=justify style=MARGIN-LEFT:0.64in>
  <img align=bottom border=0 height=630 name=graphics3 src=lab04_otchet_images/dg9jvsbd_79vgjttmdp_b.png width=542>
</p>
<p align=justify style=MARGIN-LEFT:0.64in>
  <br>
</p>
<p align=justify style=MARGIN-LEFT:0.64in>
  <br>
</p>
<ul>
  <li>
    <p align=justify>
      <font face="Times New Roman, serif"><font size=3>Поколения хромосом</font></font>
    </p>
  </li>
</ul>
<p align=justify style=MARGIN-LEFT:0.64in>
  <font face="Times New Roman, serif"><font size=3>Первое</font></font>
</p>
<p align=justify style=MARGIN-LEFT:0.93in>
  <img align=bottom border=0 height=500 name=graphics4 src=lab04_otchet_images/dg9jvsbd_80hg6tgggz_b.png width=281>
</p>
<p align=justify style=MARGIN-LEFT:0.93in>
  <font face="Times New Roman, serif"><font size=3>Второе</font></font>
</p>
<p align=justify style=MARGIN-LEFT:0.93in>
  <img align=bottom border=0 height=540 name=graphics5 src=lab04_otchet_images/dg9jvsbd_81fqtkx9qn_b.png width=275>
</p>
<p align=justify style=MARGIN-LEFT:0.93in>
  ……………………………………………………………………………………………
</p>
<p align=justify style=MARGIN-LEFT:0.93in>
  <font face="Times New Roman, serif"><font size=3>Последнее</font></font>
</p>
<p align=justify style=MARGIN-LEFT:0.93in>
  <img align=bottom border=0 height=474 name=graphics6 src=lab04_otchet_images/dg9jvsbd_82dc2j42dn_b.png width=292>
</p>
<p align=justify style=MARGIN-LEFT:0.93in>
  <br>
</p>
<h5 class=western>
  <font face="Times New Roman, serif">2.4. Выводы и рекомендации по использованию разработанных ГА.</font>
</h5>
<p class=western>
  <br>
</p>
<p align=justify class=western>
  <font size=3><font color=#000000>Из проведенных экспериментов видно, что разработанный ГА не претендует на оптимальность в данной задаче, однако справляется с ее решением.</font></font>
</p>
<br></body>
</html>